home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 15 / CU Amiga Magazine's Super CD-ROM 15 (1997)(EMAP Images)(GB)[!][issue 1997-10].iso / CUCD / Graphics / Ghostscript / source / gxpath2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-06-10  |  11.9 KB  |  442 lines
  1. /* Copyright (C) 1989, 1995, 1997 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gxpath2.c */
  20. /* Path tracing procedures for Ghostscript library */
  21. #include "math_.h"
  22. #include "gx.h"
  23. #include "gserrors.h"
  24. #include "gxfixed.h"
  25. #include "gxarith.h"
  26. #include "gzpath.h"
  27.  
  28. /* Define the enumeration structure. */
  29. private_st_path_enum();
  30.  
  31. /* Assign a path. */
  32. void
  33. gx_path_assign(gx_path *pto, const gx_path *pfrom)
  34. {    *pto = *pfrom;
  35. }
  36.  
  37. /* Read the current point of a path. */
  38. int
  39. gx_path_current_point(const gx_path *ppath, gs_fixed_point *ppt)
  40. {    if ( !path_position_valid(ppath) )
  41.       return_error(gs_error_nocurrentpoint);
  42.     /* Copying the coordinates individually */
  43.     /* is much faster on a PC, and almost as fast on other machines.... */
  44.     ppt->x = ppath->position.x, ppt->y = ppath->position.y;
  45.     return 0;
  46. }
  47.  
  48. /* Read the bounding box of a path. */
  49. /* Note that if the last element of the path is a moveto, */
  50. /* the bounding box does not include this point, */
  51. /* unless this is the only element of the path. */
  52. int
  53. gx_path_bbox(gx_path *ppath, gs_fixed_rect *pbox)
  54. {    if ( ppath->bbox_set )
  55.     {    /* The bounding box was set by setbbox. */
  56.         *pbox = ppath->bbox;
  57.         return 0;
  58.     }
  59.     if ( ppath->first_subpath == 0 )
  60.        {    /* The path is empty, use the current point if any. */
  61.         int code = gx_path_current_point(ppath, &pbox->p);
  62.  
  63.         if ( code < 0 )
  64.           { /*
  65.              * Don't return garbage, in case the caller doesn't
  66.              * check the return code.
  67.              */
  68.             pbox->p.x = pbox->p.y = 0;
  69.           }
  70.         pbox->q = pbox->p;
  71.         return code;
  72.        }
  73.     /* The stored bounding box may not be up to date. */
  74.     /* Correct it now if necessary. */
  75.     if ( ppath->box_last == ppath->current_subpath->last )
  76.        {    /* Box is up to date */
  77.         *pbox = ppath->bbox;
  78.        }
  79.     else
  80.        {    gs_fixed_rect box;
  81.         register segment *pseg = ppath->box_last;
  82.         if ( pseg == 0 )    /* box is uninitialized */
  83.            {    pseg = (segment *)ppath->first_subpath;
  84.             box.p.x = box.q.x = pseg->pt.x;
  85.             box.p.y = box.q.y = pseg->pt.y;
  86.            }
  87.         else
  88.            {    box = ppath->bbox;
  89.             pseg = pseg->next;
  90.            }
  91. /* Macro for adjusting the bounding box when adding a point */
  92. #define adjust_bbox(pt)\
  93.   if ( (pt).x < box.p.x ) box.p.x = (pt).x;\
  94.   else if ( (pt).x > box.q.x ) box.q.x = (pt).x;\
  95.   if ( (pt).y < box.p.y ) box.p.y = (pt).y;\
  96.   else if ( (pt).y > box.q.y ) box.q.y = (pt).y
  97.         while ( pseg )
  98.            {    switch ( pseg->type )
  99.                {
  100.             case s_curve:
  101. #define pcurve ((curve_segment *)pseg)
  102.                 adjust_bbox(pcurve->p1);
  103.                 adjust_bbox(pcurve->p2);
  104. #undef pcurve
  105.                 /* falls through */
  106.             default:
  107.                 adjust_bbox(pseg->pt);
  108.                }
  109.             pseg = pseg->next;
  110.            }
  111. #undef adjust_bbox
  112.         ppath->bbox = box;
  113.         ppath->box_last = ppath->current_subpath->last;
  114.         *pbox = box;
  115.        }
  116.     return 0;
  117. }
  118.  
  119. /* Test if a path has any curves. */
  120. bool
  121. gx_path_has_curves(const gx_path *ppath)
  122. {    return ppath->curve_count != 0;
  123. }
  124.  
  125. /* Test if a path has no segments. */
  126. bool
  127. gx_path_is_void(const gx_path *ppath)
  128. {    return ppath->first_subpath == 0;
  129. }
  130.  
  131. /* Test if a path has no elements at all. */
  132. bool
  133. gx_path_is_null(const gx_path *ppath)
  134. {    return ppath->first_subpath == 0 && !path_position_valid(ppath);
  135. }
  136.  
  137. /*
  138.  * Test if a subpath to be filled is a rectangle; if so, return its
  139.  * bounding box and the start of the next subpath.
  140.  * Note that this must recognize:
  141.  *    ordinary closed rectangles (M, L, L, L, C);
  142.  *    open rectangles (M, L, L, L);
  143.  *    rectangles closed with lineto (Mo, L, L, L, Lo);
  144.  *    rectangles closed with *both* lineto and closepath (bad PostScript,
  145.  *      but unfortunately not rare) (Mo, L, L, L, Lo, C).
  146.  */
  147. bool
  148. gx_subpath_is_rectangle(const subpath *pseg0, gs_fixed_rect *pbox,
  149.   const subpath **ppnext)
  150. {    const segment *pseg1, *pseg2, *pseg3, *pseg4;
  151.     if (    pseg0->curve_count == 0 &&
  152.         (pseg1 = pseg0->next) != 0 &&
  153.         (pseg2 = pseg1->next) != 0 &&
  154.         (pseg3 = pseg2->next) != 0 &&
  155.         ((pseg4 = pseg3->next) == 0 || pseg4->type != s_line ||
  156.          (pseg4->pt.x == pseg0->pt.x &&
  157.           pseg4->pt.y == pseg0->pt.y &&
  158.           (pseg4->next == 0 || pseg4->next->type != s_line)))
  159.        )
  160.        {    fixed x0 = pseg0->pt.x, y0 = pseg0->pt.y;
  161.         fixed x2 = pseg2->pt.x, y2 = pseg2->pt.y;
  162.         if (    (x0 == pseg1->pt.x && pseg1->pt.y == y2 &&
  163.              x2 == pseg3->pt.x && pseg3->pt.y == y0) ||
  164.             (x0 == pseg3->pt.x && pseg3->pt.y == y2 &&
  165.              x2 == pseg1->pt.x && pseg1->pt.y == y0)
  166.            )
  167.            {    /* Path is a rectangle.  Return the bounding box. */
  168.             if ( x0 < x2 )
  169.               pbox->p.x = x0, pbox->q.x = x2;
  170.             else
  171.               pbox->p.x = x2, pbox->q.x = x0;
  172.             if ( y0 < y2 )
  173.               pbox->p.y = y0, pbox->q.y = y2;
  174.             else
  175.               pbox->p.y = y2, pbox->q.y = y0;
  176.             while ( pseg4 != 0 && pseg4->type != s_start )
  177.               pseg4 = pseg4->next;
  178.             *ppnext = (const subpath *)pseg4;
  179.             return true;
  180.            }
  181.        }
  182.     return false;
  183. }
  184. /* Test if an entire path to be filled is a rectangle. */
  185. bool
  186. gx_path_is_rectangle(const gx_path *ppath, gs_fixed_rect *pbox)
  187. {    const subpath *pnext;
  188.     return (ppath->subpath_count == 1 &&
  189.         gx_subpath_is_rectangle(ppath->first_subpath, pbox, &pnext));
  190. }
  191.  
  192. /* Translate an already-constructed path (in device space). */
  193. /* Don't bother to update the cbox. */
  194. int
  195. gx_path_translate(gx_path *ppath, fixed dx, fixed dy)
  196. {    segment *pseg;
  197. #define update_xy(pt)\
  198.   pt.x += dx, pt.y += dy
  199.     if ( ppath->box_last != 0 )
  200.       { update_xy(ppath->bbox.p);
  201.         update_xy(ppath->bbox.q);
  202.       }
  203.     if ( path_position_valid(ppath) )
  204.       update_xy(ppath->position);
  205.     for ( pseg = (segment *)(ppath->first_subpath); pseg != 0;
  206.           pseg = pseg->next
  207.         )
  208.       switch ( pseg->type )
  209.         {
  210.         case s_curve:
  211. #define pcseg ((curve_segment *)pseg)
  212.         update_xy(pcseg->p1);
  213.         update_xy(pcseg->p2);
  214. #undef pcseg
  215.         default:
  216.         update_xy(pseg->pt);
  217.         }
  218. #undef update_xy
  219.     return 0;
  220. }
  221.  
  222. /* Scale an existing path by a power of 2 (positive or negative). */
  223. void
  224. gx_point_scale_exp2(gs_fixed_point *pt, int sx, int sy)
  225. {    if ( sx >= 0 ) pt->x <<= sx; else pt->x >>= -sx;
  226.     if ( sy >= 0 ) pt->y <<= sy; else pt->y >>= -sy;
  227. }
  228. void
  229. gx_rect_scale_exp2(gs_fixed_rect *pr, int sx, int sy)
  230. {    gx_point_scale_exp2(&pr->p, sx, sy);
  231.     gx_point_scale_exp2(&pr->q, sx, sy);
  232. }
  233. int
  234. gx_path_scale_exp2(gx_path *ppath, int log2_scale_x, int log2_scale_y)
  235. {    segment *pseg;
  236.     gx_rect_scale_exp2(&ppath->bbox, log2_scale_x, log2_scale_y);
  237. #define update_xy(pt) gx_point_scale_exp2(&pt, log2_scale_x, log2_scale_y)
  238.     update_xy(ppath->position);
  239.     for ( pseg = (segment *)(ppath->first_subpath); pseg != 0;
  240.           pseg = pseg->next
  241.         )
  242.       switch ( pseg->type )
  243.         {
  244.         case s_curve:
  245. #define pcseg ((curve_segment *)pseg)
  246.         update_xy(pcseg->p1);
  247.         update_xy(pcseg->p2);
  248. #undef pcseg
  249.         default:
  250.         update_xy(pseg->pt);
  251.         }
  252. #undef update_xy
  253.     return 0;
  254. }
  255.  
  256. /* Reverse a path. */
  257. /* We know ppath != ppath_old. */
  258. int
  259. gx_path_copy_reversed(const gx_path *ppath_old, gx_path *ppath, bool init)
  260. {    const subpath *psub = ppath_old->first_subpath;
  261.     int code;
  262.  
  263. #ifdef DEBUG
  264.     if ( gs_debug_c('P') )
  265.       gx_dump_path(ppath_old, "before reversepath");
  266. #endif
  267.     if ( init )
  268.       gx_path_init(ppath, ppath_old->memory);
  269. nsp:    while ( psub )
  270.     {    const segment *pseg = psub->last;
  271.         const segment *prev;
  272.         segment_notes prev_notes =
  273.           (pseg == (const segment *)psub ? sn_none :
  274.            psub->next->notes);
  275.         segment_notes notes;
  276.  
  277.         code = gx_path_add_point(ppath, pseg->pt.x, pseg->pt.y);
  278.         if ( code < 0 )
  279.           goto fx;
  280.         for ( ; ; pseg = prev, prev_notes = notes )
  281.         {    prev = pseg->prev;
  282.             notes = pseg->notes;
  283.             prev_notes = (prev_notes & sn_not_first) |
  284.               (notes & ~sn_not_first);
  285.             switch ( pseg->type )
  286.             {
  287.             case s_start:
  288. endsp:                /* Finished subpath */
  289.                 if ( psub->is_closed )
  290.                 {    code =
  291.                       gx_path_close_subpath_notes(ppath,
  292.                         prev_notes);
  293.                     if ( code < 0 )
  294.                       goto fx;
  295.                 }
  296.                 psub = (const subpath *)psub->last->next;
  297.                 goto nsp;
  298.             case s_curve:
  299.             {    const curve_segment *pc =
  300.                   (const curve_segment *)pseg;
  301.  
  302.                 code = gx_path_add_curve_notes(ppath,
  303.                     pc->p2.x, pc->p2.y,
  304.                     pc->p1.x, pc->p1.y,
  305.                     prev->pt.x, prev->pt.y, prev_notes);
  306.                 break;
  307.             }
  308.             case s_line:
  309.             case s_line_close:
  310.                 if ( prev->type == s_start && psub->is_closed )
  311.                 {    pseg = prev;
  312.                     goto endsp;
  313.                 }
  314.                 code = gx_path_add_line_notes(ppath,
  315.                     prev->pt.x, prev->pt.y, prev_notes);
  316.                 break;
  317.             }
  318.             if ( code < 0 )
  319.               goto fx;
  320.         }
  321.         /* not reached */
  322.     }
  323. #undef sn_not_end
  324.     if ( path_last_is_moveto(ppath_old) )
  325.     {    code = gx_path_add_point(ppath, ppath_old->position.x,
  326.                      ppath_old->position.y);
  327.         if ( code < 0 )
  328.           goto fx;
  329.     }
  330. #ifdef DEBUG
  331. if ( gs_debug_c('P') )
  332.     gx_dump_path(ppath, "after reversepath");
  333. #endif
  334.     return 0;
  335. fx:    gx_path_release(ppath);
  336.     return code;
  337. }
  338.  
  339. /* ------ Path enumeration ------ */
  340.  
  341. /* Allocate a path enumerator. */
  342. gs_path_enum *
  343. gs_path_enum_alloc(gs_memory_t *mem, client_name_t cname)
  344. {    return gs_alloc_struct(mem, gs_path_enum, &st_gs_path_enum, cname);
  345. }
  346.  
  347. /* Start enumerating a path. */
  348. int
  349. gx_path_enum_init(gs_path_enum *penum, const gx_path *ppath)
  350. {    penum->path = ppath;
  351.     penum->copied_path = 0;        /* not copied */
  352.     penum->pgs = 0;
  353.     penum->pseg = (const segment *)ppath->first_subpath;
  354.     penum->moveto_done = false;
  355.     penum->notes = sn_none;
  356.     return 0;
  357. }
  358.  
  359. /* Enumerate the next element of a path. */
  360. /* If the path is finished, return 0; */
  361. /* otherwise, return the element type. */
  362. int
  363. gx_path_enum_next(gs_path_enum *penum, gs_fixed_point ppts[3])
  364. {    const segment *pseg = penum->pseg;
  365.  
  366.     if ( pseg == 0 )
  367.     {    /* We've enumerated all the segments, but there might be */
  368.         /* a trailing moveto. */
  369.         const gx_path *ppath = penum->path;
  370.         if ( path_last_is_moveto(ppath) && !penum->moveto_done )
  371.         {    /* Handle a trailing moveto */
  372.             penum->moveto_done = true;
  373.             penum->notes = sn_none;
  374.             ppts[0] = ppath->position;
  375.             return gs_pe_moveto;
  376.         }
  377.         return 0;
  378.     }
  379.     penum->pseg = pseg->next;
  380.     penum->notes = pseg->notes;
  381.     switch ( pseg->type )
  382.        {
  383.     case s_start:
  384.          ppts[0] = pseg->pt;
  385.          return gs_pe_moveto;
  386.     case s_line:
  387.          ppts[0] = pseg->pt;
  388.          return gs_pe_lineto;
  389.     case s_line_close:
  390.          ppts[0] = pseg->pt;
  391.          return gs_pe_closepath;
  392.     case s_curve:
  393. #define pcseg ((const curve_segment *)pseg)
  394.          ppts[0] = pcseg->p1;
  395.          ppts[1] = pcseg->p2;
  396.          ppts[2] = pseg->pt;
  397.          return gs_pe_curveto;
  398. #undef pcseg
  399.     default:
  400.          lprintf1("bad type %x in gx_path_enum_next!\n", pseg->type);
  401.          return_error(gs_error_Fatal);
  402.        }
  403. }
  404.  
  405. /* Return the notes from the last-enumerated segment. */
  406. segment_notes
  407. gx_path_enum_notes(const gs_path_enum *penum)
  408. {    return penum->notes;
  409. }
  410.  
  411. /* Back up 1 element in the path being enumerated. */
  412. /* Return true if successful, false if we are at the beginning of the path. */
  413. /* This implementation allows backing up multiple times, */
  414. /* but no client currently relies on this. */
  415. bool
  416. gx_path_enum_backup(gs_path_enum *penum)
  417. {    const segment *pseg = penum->pseg;
  418.  
  419.     if ( pseg != 0 )
  420.       {    if ( (pseg = pseg->prev) == 0 )
  421.           return false;
  422.         penum->pseg = pseg;
  423.         return true;
  424.       }
  425.     /* We're at the end of the path.  Check to see whether */
  426.     /* we need to back up over a trailing moveto. */
  427.     { const gx_path *ppath = penum->path;
  428.       if ( path_last_is_moveto(ppath) && penum->moveto_done )
  429.         { /* Back up over the trailing moveto. */
  430.           penum->moveto_done = false;
  431.           return true;
  432.         }
  433.       { const subpath *psub = ppath->current_subpath;
  434.         if ( psub == 0 )        /* empty path */
  435.           return false;
  436.         /* Back up to the last segment of the last subpath. */
  437.         penum->pseg = psub->last;
  438.         return true;
  439.       }
  440.     }
  441. }
  442.